20220306-TIL

오늘 알고리즘 문제는 처음부터 접근을 잘못해서 못 풀었다. (문제의 핵심을 파악하질 못했다;)

• Ignition 문제는 모든 간선에 대해, ‘간선이 타서 없어지는 시점’ 을 알아내야 하는 문제였다.
• 처음에는 마지막에 사라질 간선만 구하면 된다는 식으로 접근했다. (풀이가 이어지질 않는;)
  (너비 우선 탐색, 백트래킹을 활용해보려 해봤지만, 정확하게 계산해낼 방법이 생각이 안 났다..)
• 어떤 정점에 불을 붙였을 때, 어떤 간선이 다 타기까지의 시간을 알아내는 것이 핵심이었다.
• 불씨가 시작되는 정점 s와 임의의 간선 (i, j) 사이의 관계를 밝혀내는 부분이 특히 중요했다.
  ((i, j) 간선이 다 타기까지 걸리는 시간 = s, i, j를 꼭짓점으로 하는 삼각형의 둘레 / 2)
• 플로이드 알고리즘을 이용해 불씨가 도달하는 가장 빠른 시간을 기록해두는 것도 중요했다.

‘컴퓨터 구조 기초’ 의 내용을 수정했다. (그림만 보고 자료 탐색 + 내용 정리까지.. 쉽지 않다;;)

• 페이지 디렉터리, 다단계 페이징 관련 내용을 수정했다. (역시 처음부터 제대로 배우는 게..)